90 分做法,所以这篇就不投题解了
设 为抽了 张卡还没有成功的方案数, 和 与题面意义相同,则有
尝试展开 ,考虑枚举抽了 轮之后手里有的不同的卡的数量是 。同时设 代表限定了 张卡抽了 轮每张卡都抽到的方案数, 代表选择了 张不同的卡没有出现 连号的方案数:
(这里把 特判出来了,因为留着它不利于后面式子展开)
是一个经典的球盒模型,它等于 个不同的球放进 个不同的盒子,且每个盒子都有球的方案数。很容易容斥求出:
对原式改变求和顺序,把对 的求和挪到里面,然后利用等比数列无穷项的求和公式:
把组合数展开,发现这玩意是一个卷积的形式,还可以用 NTT 优化,以 的复杂度计算出对于所有 的值。我们先把他记作 然后放在这。
接下来优化 。这东西可以分段计算,原卡组形成了若干个连续段,可以单独计算每个连续段。在一个长度为 的段里选择选择 张卡没有 连号的方案数,隔板法转化一下其实也是球盒模型,它等于 个一样的球丢进 个不同的盒,且每个盒里的球小于 个的方案数。照样容斥计算。
直接照着这个式子计算,总体时间复杂度是 ,能拿90分(省选要是能拿 90 分够香了吧)。满分做法就是把这个地方改成生成函数求,然而我并不会(
把每个连续段的答案合并其实就是背包合并,还是可以 NTT 优化。把两个大小为 和 的背包合并需要花费 的时间,形成一个大小为 的背包。这明显就是 P1090 合并果子 的模型,开个优先队列,每次合并两个最小的,可以证明这样做的总复杂度是 。(倒数第 次合并的两个背包长度和不会超过 ,总长度和是 )
全都合并起来之后剩下的那个背包就是 的值,和刚才求出的 做个点积加上 输出就做完了。
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#define M 200001
#define L (1<<19)
#define P 998244353
int m, k; bool mk[2*M];
int pow(int b, int p) {
if (p < 0) p += P-1;
long long a = b, ret = 1;
while (p) {
if (p & 1) ret = ret * a % P;
a = a * a % P;
p >>= 1;
}
return ret;
}
int ln2(int x) {return 32-__builtin_clz(x-1); }
int r[L], a[L], b[L];
void NTT(int* a, int f, int n) {
for (int i = 0; i < n; i++)
if (i < r[i]) std::swap(a[i], a[r[i]]);
for (int l = 1; 2*l <= n; l <<= 1) {
int w = pow(3, f*(P-1)/(2*l));
for (int i = 0; i < n; i += 2*l) {
long long d = 1;
for (int k = 0; k < l; k++) {
int u = a[i+k], v = a[i+l+k];
a[i+k] = (d * v + u) % P;
a[i+l+k] = ((P-d) * v + u) % P;
d = d * w % P;
}
}
}
}
void mul(int ln) {
#define N (1<<ln)
for (int i = 1; i < N; i++)
r[i] = (r[i>>1]>>1) | ((i&1)<<(ln-1));
NTT(a, 1, N);
NTT(b, 1, N);
long long x = pow(1<<ln, -1);
for (int i = 0; i < N; i++)
a[i] = x * a[i] % P * b[i] % P;
NTT(a, -1, N);
}
std::vector<int> G[M]; int sz = 0;
int fi[M], fv[M], H[M];
int C(int n, int m) {
return 1ll * fi[n] * fv[m] % P * fv[n-m] % P;
}
int T1(int n, int p) {
int rs = 0;
for (int t = 0; t <= n-p+1 && t*k <= p; t++) {
int xx = 1ll * C(n-p+1, t) * C(n-t*k, n-p) % P;
if (t & 1) xx = P-xx;
rs = (rs + xx) % P;
}
return rs;
}
void work(int x) {
G[sz].push_back(1);
for (int i = 1; i <= x; i++)
G[sz].push_back(T1(x, i));
while (!G[sz].back()) G[sz].pop_back();
sz++;
}
int main() {
scanf("%d%d", &m, &k);
fi[0] = 1;
for (int i = 1; i <= m; i++)
fi[i] = 1ll * fi[i-1] * i % P;
fv[m] = pow(fi[m], -1);
for (int i = m; i >= 1; i--)
fv[i-1] = 1ll * fv[i] * i % P;
for (int i = 0, x; i < m; i++)
{scanf("%d", &x); mk[x] = true; }
for (int i = 2*m, x = 0; i >= 0; i--) {
if (!mk[i]) {if (x) work(x); x = 0; }
else x++;
}
for (int i = 0; i < m-1; i++) {
a[i] = fv[i];
if (i & 1) a[i] = P-a[i];
b[i] = 1ll * fv[i] * pow(m-i-1, -1) % P;
}
int ln = ln2(2*m-3);
mul(ln);
for (int i = 1; i < m; i++)
H[i] = 1ll * fi[i] * a[i-1] % P;
auto cmp = [](int x, int y) {return G[x].size() > G[y].size(); };
std::priority_queue<int, std::vector<int>, decltype(cmp)> pq(cmp);
for (int i = 0; i < sz; i++) pq.push(i);
while (pq.size() > 1) {
int x = pq.top(); pq.pop();
int y = pq.top(); pq.pop();
int sx = G[x].size(), sy = G[y].size();
int ln = ln2(sx+sy-1);
memcpy(a, G[x].data(), sx * sizeof(int));
memcpy(b, G[y].data(), sy * sizeof(int));
memset(a+sx, 0, ((1<<ln)-sx) * sizeof(int));
memset(b+sy, 0, ((1<<ln)-sy) * sizeof(int));
mul(ln);
G[x] = std::vector<int>(a, a+sx+sy-1);
G[y].clear();
pq.push(x);
}
int x = pq.top(), ans = 1;
for (int i = 1; i < G[x].size(); i++)
ans = (1ll * H[i] * G[x][i] + ans) % P;
printf("%d\n", ans);
}